// 提交链接 https://leetcode.cn/problems/count-complete-tree-nodes/submissions/565394766/
// 222. 完全二叉树的节点个数
// 完成日期： 2024.9.17
// 二分搜索
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        int head = 0, tail = 50000;
        while (head < tail)
        {
            int mid = (head + tail) / 2 + 1;
            if (solve(mid, root)) head = mid;
            else tail = mid - 1;
        }
        return head;
    }
    TreeNode* solve(int mid, TreeNode*& root)
    {
        if (mid == 1) return root;
        TreeNode* temp = solve(mid / 2, root);
        if (!temp) return 0;
        if (mid % 2) return temp->right;
        else return temp->left;
    }
};